package ntu.sna;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.apache.commons.collections15.Factory;

import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
import edu.uci.ics.jung.graph.Graph;

public class ESPowerLawGenerator<V, E> implements 
        GraphGenerator<V, E> {
    private int mNumVertices;
    private int mNumEdges;
    private int mNumIterations;
    private double mMaxDegree;
    private Random mRandom;
    private Factory<Graph<V, E>> graphFactory;
    private Factory<V> vertexFactory;
    private Factory<E> edgeFactory;

    public ESPowerLawGenerator(Factory<Graph<V, E>> graphFactory,
            Factory<V> vertexFactory, Factory<E> edgeFactory,
            int numVertices, int numEdges, int r) {
        this .graphFactory = graphFactory;
        this .vertexFactory = vertexFactory;
        this .edgeFactory = edgeFactory;
        mNumVertices = numVertices;
        mNumEdges = numEdges;
        mNumIterations = r;
        mRandom = new Random();
    }

    protected Graph<V, E> initializeGraph() {
        Graph<V, E> graph = null;
        graph = graphFactory.create();
        for (int i = 0; i < mNumVertices; i++) {
            graph.addVertex(vertexFactory.create());
        }
        List<V> vertices = new ArrayList<V>(graph.getVertices());
        while (graph.getEdgeCount() < mNumEdges) {
            V u = vertices
                    .get((int) (mRandom.nextDouble() * mNumVertices));
            V v = vertices
                    .get((int) (mRandom.nextDouble() * mNumVertices));
            if (!graph.isSuccessor(v, u)) {
                graph.addEdge(edgeFactory.create(), u, v);
            }
        }

        double maxDegree = 0;
        for (V v : graph.getVertices()) {
            maxDegree = Math.max(graph.degree(v), maxDegree);
        }
        mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2;

        return graph;
    }

    public Graph<V, E> create() {
        Graph<V, E> graph = initializeGraph();

        List<V> vertices = new ArrayList<V>(graph.getVertices());
        for (int rIdx = 0; rIdx < mNumIterations; rIdx++) {
            // do powerlaw alg
            V v = null;
            int degree = 0;
            do {
                v = vertices
                        .get((int) (mRandom.nextDouble() * mNumVertices));
                degree = graph.degree(v);

            } while (degree == 0);

            List<E> edges = new ArrayList<E>(graph.getIncidentEdges(v));
            E randomExistingEdge = edges.get((int) (mRandom
                    .nextDouble() * degree));

            V x = vertices
                    .get((int) (mRandom.nextDouble() * mNumVertices));
            V y = null;
            do {
                y = vertices
                        .get((int) (mRandom.nextDouble() * mNumVertices));

            } while (mRandom.nextDouble() > ((graph.degree(y) + 1) / mMaxDegree));
            

            if (!graph.isSuccessor(y, x) && x != y) {
                graph.removeEdge(randomExistingEdge);
                graph.addEdge(edgeFactory.create(), x, y);
            }
        }

        return graph;
    }

    public void setSeed(long seed) {
        mRandom.setSeed(seed);
    }
}
